/**
 * 面试题 08.05. 递归乘法
 * https://leetcode-cn.com/problems/recursive-mulitply-lcci/
 */
public class Solutions_mianshi_08_05 {
    public static void main(String[] args) {
//        int A = 1, B = 10;  // output: 10
//        int A = 3, B = 4;  // output: 12
        int A = 4, B = 6;  // output: 24

        int result = multiply(A, B);
        System.out.println(result);
    }

    /**
     * 解题思路：快速幂思想
     */
    public static int multiply(int A, int B) {
        if (B < A) {
            // 使 A 更小一些
            return multiply(B, A);
        }
        return recursion(A, B);
    }

    public static int recursion(int A, int B) {
        if (A == 1) {
            return B;
        }
        if ((A & 1) == 0) {
            // 偶数（2 * 4 = 8）
            return recursion(A >> 1, B << 1);
        } else {
            // 奇数（2 * 4 + 4 = 12）
            return recursion(A >> 1, B << 1) + B;
        }
    }
}
